package com.jankins.pat;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

public class BikeManager {
    public static int INFINITY = Integer.MAX_VALUE;
    public final int MAX_CAPACITY_VALUE;

    private int[] capacity;

    private int target;
    private int source;

    private Graph g;

    // shortest pathes fields
    private int[] distTo;
    private List<Integer>[] pre;
    private PriorityQueue<Integer> pq;

    @SuppressWarnings("unchecked")
    public BikeManager(Scanner in) {
        MAX_CAPACITY_VALUE = in.nextInt();
        int n = in.nextInt();

        target = in.nextInt();
        int m = in.nextInt();

        capacity = new int[n + 1];
        capacity[0] = INFINITY;
        for(int i = 1; i <= n; i++) {
            capacity[i] = in.nextInt();
        }

        this.g = new Graph(n+1, m);

        for(int i = 0; i < g.E; i++) {
            int v = in.nextInt();
            int w = in.nextInt();
            int weight = in.nextInt();

            g.addEdge(new Edge(v, w, weight));
        }

        // dijkstra algorithm - find the shortest path to target 
        distTo = new int[n + 1];
        pre = (List<Integer>[]) new List[n + 1];
        pq = new PriorityQueue<Integer>((v, w) -> distTo[v] - distTo[w]);

        source = 0;
        dijkstra(source);
    }

    public void dijkstra(int s) {
        // initial
        for(int i = 0; i < g.V; i++) {
            distTo[i] = INFINITY;
            pre[i] = new ArrayList<>();
            pq.add(i);
        }
        distTo[s] = 0;

        while(!pq.isEmpty()) {
            int v = pq.poll();

            // check if we have arrive the target
            if(v == target) break;

            // relaxation
            for(Edge e : g.adj[v]) {
                int w = e.other(v);
                if(distTo[w] > distTo[v] + e.weight) {
                    distTo[w] = distTo[v] + e.weight;
                    pre[w].clear();
                    pre[w].add(v);
                } else if (distTo[w] == distTo[v] + e.weight) {
                    pre[w].add(v);
                }
            }
        } // end dijkstra algorithm
    }

    private Deque<Integer> path;
    private Deque<Integer> marked;
    private int sent = INFINITY;

    public Deque<Integer> shortesPath() {
        marked = new LinkedList<Integer>();

        dfs(target, 0);

        return path;
    }

    private void dfs(int v, int cal) {
        marked.push(v);

        if(v == source) {
            if(sent > cal) {
                sent = cal;
                path = new LinkedList<>(marked);
            }
            // bracktracking
            marked.remove(v);
            return;
        }

        cal += MAX_CAPACITY_VALUE / 2 - capacity[v];

        for(int w : pre[v]) {
            if(!marked.contains(w)) {
                dfs(w, cal);
            }
        }
        marked.remove(v);
    }

    private class Graph {
        int V;
        int E;
        List<Edge>[] adj;

        @SuppressWarnings("unchecked")
        public Graph(int V, int E) {
            this.V = V;
            this.E = E;
            adj = (List<Edge>[]) new List[V];

            for(int i = 0; i < V; i++) {
                adj[i] = new ArrayList<Edge>();
            }
        }

        public void addEdge(Edge e) {
          int v = e.either();
          int w = e.other(v);

          adj[v].add(e);
          adj[w].add(e);
        }
    }

    private class Edge {
        int v;
        int w;
        int weight;

        public Edge(int v, int w, int weight) {
            this.v = v;
            this.w = w;
            this.weight = weight;
        }

        public int either() {
            return v;
        }

        public int other(int v) {
            if(this.v != v) return this.v;
            else if (this.w != v) return w;
            else return v;
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        BikeManager bikeManager = new BikeManager(in);

        System.out.println(bikeManager.distTo[bikeManager.target]);
        Deque<Integer> sp = bikeManager.shortesPath();

        System.out.println(bikeManager.sent);
    }
}
